home *** CD-ROM | disk | FTP | other *** search
/ HPAVC / HPAVC CD-ROM.iso / VELENG10.ZIP / PNSEARCH.C < prev    next >
C/C++ Source or Header  |  1997-07-27  |  27KB  |  1,182 lines
  1. // ****************************************************************************
  2. // *                                                                          *
  3. // *                      Velena Source Code V1.0                             *
  4. // *                   Written by Giuliano Bertoletti                         *
  5. // *       Based on the knowledged approach of Louis Victor Allis             *
  6. // *   Copyright (C) 1996-97 by Giuliano Bertoletti & GBE 32241 Software PR   *
  7. // *                                                                          *
  8. // ****************************************************************************
  9.  
  10. // Portable engine version.
  11. // read the README file for further informations.
  12.  
  13. // ==========================================================================
  14.  
  15.  
  16. #include <stdio.h>
  17. #include <string.h>
  18. #include <stdlib.h>
  19. #include <malloc.h>
  20. #include <time.h>
  21.  
  22. #include "connect4.h"
  23. #include "con4vals.h"
  24. #include "rules.h"
  25. #include "pnsearch.h"
  26. #include "proto.h"
  27.  
  28. #define AUTO_BOOK "autobook.cn4"
  29.  
  30. #define SCREENSAVER 10
  31.  
  32. #define DATABASEFILE    "openbook.cn4"
  33. #define DATABASELOGFILE "openbook.log"
  34.  
  35. #define BADDATABASEFILE "openbook.bad"
  36. #define NEWDATABASEFILE "openbook.new"
  37.  
  38. short nodeseq[]={ 3,2,4,5,1,0,6 };  // This is the sequence we follow to
  39.                                     // scan the seven moves available
  40.  
  41. unsigned short *myscreen,saveflag;
  42.  
  43. char *tr[]={"None","White (O)","Black (X)"};
  44.  
  45. long max_nodes_numb,node_expanded,node_not_expanded;
  46. long nodes_added;
  47. short timepass,noscreensaver=NO;
  48. short best_keep;
  49. short manual_steer;
  50.  
  51. long my_t_sequence;
  52.  
  53. struct board *auxboard,*tempboard;
  54. struct node *root;
  55. struct bintree *treeroot;
  56. struct dbtree *dbroot;
  57.  
  58. struct parameters parameters;
  59.  
  60. short rootsym,currsym;
  61.  
  62. void steering(short steer)
  63.     {
  64.     manual_steer=steer;
  65.     }
  66.  
  67. short compatible_sym(unsigned char *p1,unsigned char *p2)
  68.     {
  69.     short x;
  70.  
  71.     for(x=0;x<BOARDX && p1[x]!=EMPTY && p2[x]!=EMPTY;x++)
  72.         if(p1[x]!=p2[x]) return YES;
  73.  
  74.     return NO;
  75.     }
  76.  
  77. void show_pinfo()
  78.     {
  79.     short a;
  80.     char *adv[]={ "Adv White","Adv Black","Deuce" };
  81.     unsigned long tm;
  82.     short x;
  83.     short hh,mm,ss;
  84.     char st[80],seqs[10];
  85.  
  86.     if(manual_steer) strcpy(seqs,"None");
  87.     else sprintf(seqs,"%-4ld",my_t_sequence);
  88.  
  89.     if(root->proof==root->disproof) a=2;
  90.     else
  91.         {
  92.         if(root->turn==WHITE)
  93.             {
  94.             if(root->proof<root->disproof) a=0;
  95.             else a=1;
  96.             }
  97.         else
  98.             {
  99.             if(root->proof<root->disproof) a=1;
  100.             else a=0;
  101.             }
  102.         }
  103.  
  104.     memset(st,0x20,80);
  105.  
  106.     parameters.maxnodes=max_nodes_numb;
  107.     tm=parameters.end-parameters.start;
  108.  
  109.     hh=(short)(tm/3600);
  110.     mm=(short)((tm/60)%60);
  111.     ss=(short)(tm%60);
  112.  
  113.     if(parameters.pr>0 && parameters.ds>0)
  114.         {
  115.         sprintf(st," Nodes: %5ld/%-5ld   P=%-3d   D=%-3d   Time: %2d:%02d:%02d   SEQ=%s   %s",
  116.                 parameters.nodes,parameters.maxnodes,parameters.pr,parameters.ds,hh,mm,ss,
  117.                 seqs,adv[a]);
  118.         }
  119.     else if(parameters.pr==0)
  120.         {
  121.         sprintf(st," Nodes: %5ld/%-5ld   P=%-3c   D=%-3c   Time: %2d:%02d:%02d   SEQ=%s   %s",
  122.                 parameters.nodes,parameters.maxnodes,'φ','∞',hh,mm,ss,
  123.                 seqs,adv[a]);
  124.         }
  125.     else if(parameters.ds==0)
  126.         {
  127.         sprintf(st," Nodes: %5ld/%-5ld   P=%-3c   D=%-3c   Time: %2d:%02d:%02d   SEQ=%s   %s",
  128.                 parameters.nodes,parameters.maxnodes,'∞','φ',hh,mm,ss,
  129.                 seqs,adv[a]);
  130.         }
  131.  
  132.     for(x=0;x<78;x++)
  133.         myscreen[x]=0x1e00+st[x];
  134.  
  135.     if(noscreensaver) myscreen[78]=0x1e00+'S';
  136.     else myscreen[78]=0x1e00+' ';
  137.     }
  138.  
  139. /* ------------------------------------------------------------------- */
  140.  
  141. void change_max_nodes_numb(void)
  142.     {
  143.     long nodes;
  144.  
  145.     printf("\n");
  146.     printf("Enter new number of nodes (old is %ld) : ",max_nodes_numb);
  147.     scanf("%ld",&nodes);
  148.  
  149.     if(nodes>0L && nodes<1000000L)
  150.         {
  151.         max_nodes_numb=nodes;
  152.         printf("%ld nodes accepted (%ld bytes)\n\n",
  153.             max_nodes_numb,max_nodes_numb*sizeof(struct node));
  154.         }
  155.     else printf("Number refused...           \n\n");
  156.     }
  157.  
  158. void change_sequence()
  159.     {
  160.     short seq[BOARDX],done[BOARDX],x,valid=YES;
  161.  
  162.     for(x=0;x<BOARDX;x++)
  163.         done[x]=NO;
  164.  
  165.     printf("\n");
  166.     printf("Enter new searching sequence\n");
  167.  
  168.     scanf("%d%d%d%d%d%d%d",&seq[0],&seq[1],&seq[2],&seq[3],
  169.                                   &seq[4],&seq[5],&seq[6]);
  170.  
  171.     for(x=0;x<BOARDX && valid;x++)
  172.         {
  173.         if(seq[x]<1 || seq[x]>BOARDX) valid=NO;
  174.         else done[seq[x]-1]=YES;
  175.         }
  176.  
  177.     for(x=0;x<BOARDX && valid;x++)
  178.         if(!done[x]) valid=NO;
  179.  
  180.     if(valid)
  181.         {
  182.         for(x=0;x<BOARDX;x++)
  183.             nodeseq[x]=seq[x]-1;
  184.  
  185.         printf("Sequence accepted!\n\n");
  186.         }
  187.     else printf("Sequence refused!\n\n");
  188.     }
  189.  
  190. void dump_pnboard(struct node *mynode)
  191.     {
  192.     short x,y,cn,x1;
  193.  
  194.     printf("\n");
  195.     printf("Root status position:\n\n");
  196.  
  197.     for(y=0;y<BOARDY;y++)
  198.         {
  199.         for(x=0;x<BOARDX;x++)
  200.             {
  201.             if(!rootsym) x1=x;
  202.             else x1=BOARDX-1-x;
  203.  
  204.             cn=mynode->square[ELM(x1,BOARDY-1-y)];
  205.             if(cn==EMPTY) printf(".");
  206.             else if(cn==WHITE) printf("O");
  207.             else if(cn==BLACK) printf("X");
  208.             else fatal_error("#@!=?");
  209.             }
  210.         printf("\n");
  211.         }
  212.  
  213.     printf("\n");
  214.     printf("%s is to move\n\n",tr[mynode->turn]);
  215.     }
  216.  
  217. void generate_all_children(struct node *node)
  218.     {
  219.     struct node *dummy,*symm;
  220.     short x,y,x1,y1,backtrace;
  221.  
  222.     for(x=0;x<BOARDX;x++)
  223.         {
  224.         if(node->child[x]) fatal_error("Tried to allocate a node twice!");
  225.         else if(node->stack[x]<BOARDY)
  226.             {
  227.             node->child[x]=(struct node *)malloc(sizeof(struct node));
  228.             symm=(struct node *)malloc(sizeof(struct node));
  229.  
  230.             if(!node->child[x] || !symm)
  231.                 fatal_error("Not enough memory to build the tree");
  232.  
  233.             memcpy(node->child[x]->square,node->square,(BOARDX+1)*(BOARDY+2));
  234.             memcpy(node->child[x]->stack,node->stack,BOARDX+1);
  235.             backtrace=x;
  236.  
  237.             node->child[x]->square[ELM(x,node->child[x]->stack[x]++)]=node->turn;
  238.             node->child[x]->turn=node->turn^SWITCHSIDE;
  239.             symm->turn=node->turn^SWITCHSIDE;
  240.  
  241.             for(y1=0;y1<BOARDY;y1++)
  242.                 {
  243.                 symm->square[ELM(BOARDX,y1)]=node->child[x]->square[ELM(BOARDX,y1)];
  244.                 for(x1=0;x1<BOARDX;x1++)
  245.                     symm->square[ELM(x1,y1)]=node->child[x]->square[ELM(BOARDX-x1-1,y1)];
  246.                 }
  247.  
  248.             symm->stack[BOARDX]=node->child[x]->stack[BOARDX];
  249.             for(x1=0;x1<BOARDX;x1++)
  250.                 symm->stack[x1]=node->child[x]->stack[BOARDX-x1-1];
  251.  
  252.             if(bin_compare(symm->square,node->child[x]->square)>0)
  253.                 {
  254.                 dummy=symm;
  255.                 symm=node->child[x];
  256.                 node->child[x]=dummy;
  257.                 backtrace=BOARDX-x-1;
  258.                 }
  259.  
  260.             dummy=check_node(treeroot,node->child[x],0);
  261.             if(dummy)
  262.                 {
  263.                 free(node->child[x]);
  264.                 node->child[x]=dummy;
  265.                 node->child[x]->parent[backtrace]=node;
  266.                 node_not_expanded++;
  267.                 }
  268.             else
  269.                 {
  270.                 node->child[x]->expanded=NO;
  271.                 node->child[x]->evaluated=NO;
  272.                 node->child[x]->direct=YES;
  273.  
  274.                 for(y=0;y<BOARDX;y++)
  275.                     node->child[x]->parent[y]=NULL;
  276.  
  277.                 node->child[x]->parent[backtrace]=node;
  278.  
  279.                 for(y=0;y<BOARDX;y++)
  280.                     node->child[x]->child[y]=NULL;
  281.  
  282.                 node_expanded++;
  283.  
  284.                 if(node->type==AND_TYPE) node->child[x]->type=OR_TYPE;
  285.                 else if(node->type==OR_TYPE) node->child[x]->type=AND_TYPE;
  286.                 else fatal_error("Could not recognize node type!");
  287.  
  288.                 /*add_node(treeroot,node->child[x]);*/
  289.                 }
  290.  
  291.             node->symmetric[x]=backtrace;
  292.             free(symm);
  293.             }
  294.  
  295.         else node->child[x]=NULL;
  296.         }
  297.     }
  298.  
  299. short think_function(struct board *board)
  300.     {
  301.     return -evaluation_function(board);
  302.     }
  303.  
  304. void evaluate(struct node *node)
  305.     {
  306.     short x,oracle,value,flag=YES;
  307.  
  308.     if(node->evaluated)
  309.         {
  310.         printf("!");
  311.         return;
  312.         }
  313.  
  314.     value=test_dbtree_position(dbroot,node->square);
  315.  
  316.     if(value!=0)
  317.         {
  318.         flag=NO;
  319.         if(value==PROVED)
  320.             {
  321.             if(root->turn==WHITE) node->value=PROVED;
  322.             else node->value=DISPROVED;
  323.             }
  324.         else
  325.             {
  326.             if(root->turn==WHITE) node->value=DISPROVED;
  327.             else node->value=PROVED;
  328.             }
  329.  
  330.         node->evaluated=YES;
  331.         goto BYE_BYE;
  332.         }
  333.  
  334.     myscreen[79]=0x2b20;
  335.     if(heuristic_search(node,2800L)) goto BYE_BYE;
  336.  
  337.     myscreen[79]=0x4b20;
  338.  
  339.     for(x=0;x<64;x++)
  340.         auxboard->square[x]=(short)node->square[x];
  341.  
  342.     auxboard->turn=node->turn;
  343.     auxboard->filled=0;
  344.  
  345.     for(x=0;x<BOARDX+1;x++)
  346.         {
  347.         auxboard->stack[x]=(short)node->stack[x];
  348.         if(x<BOARDX) auxboard->filled+=auxboard->stack[x];
  349.         }
  350.  
  351.     if(auxboard->filled<MAXMEN) oracle=think_function(auxboard);
  352.     else fatal_error("I thought I never would have come here...");
  353.  
  354.     if(oracle==NO) node->value=UNKNOWN;
  355.     else if(oracle==-1)
  356.         {
  357.         if(node->type==OR_TYPE) node->value=DISPROVED;
  358.         else node->value=PROVED;
  359.         }
  360.     else if(oracle==YES)
  361.         {
  362.         if(node->type==OR_TYPE) node->value=PROVED;
  363.         else node->value=DISPROVED;
  364.         }
  365.     else fatal_error("Oracle got crazy!");
  366.  
  367.     BYE_BYE:
  368.     if(node->value==UNKNOWN) printf("?");
  369.     else if(node->value==PROVED)
  370.         {
  371.         if(flag) printf("+");
  372.         else printf("*");
  373.         }
  374.     else
  375.         {
  376.         if(flag) printf("-");
  377.         else printf("=");
  378.         }
  379.  
  380.     myscreen[79]=0x1b20;
  381.     }
  382.  
  383. void free_whole_tree(struct bintree *tree)
  384.     {
  385.     short x;
  386.  
  387.     if(!tree) return;
  388.     if(tree->lson) free_whole_tree(tree->lson);
  389.     if(tree->rson) free_whole_tree(tree->rson);
  390.  
  391.     free(tree->node);
  392.     }
  393.  
  394. /* ------------------------------------------------------------------- */
  395.  
  396. short resources_available()
  397.     {
  398.     short key;
  399.  
  400.     key=readkey();
  401.  
  402.     if(key==0 && timepass<SCREENSAVER)
  403.         {
  404.         timepass++;
  405.         if(timepass==SCREENSAVER && !noscreensaver) screen_off();
  406.         }
  407.     else if(key!=0)
  408.         {
  409.         timepass=0;
  410.         screen_on();
  411.         }
  412.  
  413.     switch(key)
  414.         {
  415.         case 'h':
  416.             printf("\n");
  417.             printf("Keys available:\n");
  418.             printf("ESC - abort search\n");
  419.             printf(" p  - pause search\n");
  420.             printf(" d  - dump start board status\n");
  421.             printf(" c  - change search sequence\n");
  422.             printf(" n  - change max. nodes number\n");
  423.             printf(" o  - turn on screen saver immediately\n");
  424.             printf(" h  - show this help screen\n");
  425.             printf(" s  - toggle screen saver on/off\n");
  426.             printf("\n");
  427.             break;
  428.  
  429.         case 0x1b:
  430.             printf("\n");
  431.             printf("Interrupted by user!\n");
  432.             return NO;
  433.  
  434.         case 'p':
  435.             while(readkey()==0);
  436.             break;
  437.  
  438.         case 'd':
  439.             dump_pnboard(root);
  440.             break;
  441.  
  442.         case 'c':
  443.             change_sequence();
  444.             break;
  445.  
  446.         case 'n':
  447.             change_max_nodes_numb();
  448.             break;
  449.  
  450.         case 'o':
  451.             screen_off();
  452.             break;
  453.  
  454.         case 's':
  455.             noscreensaver^=1;
  456.             printf("\n");
  457.             if(noscreensaver) printf("Screen saver is turned off\n");
  458.             else printf("Screen saver is turned on\n");
  459.             printf("\n");
  460.             break;
  461.         }
  462.  
  463.     printf(" Nod. %6ld %4ld %4ld> ",node_expanded,root->proof,root->disproof);
  464.     if(node_expanded>max_nodes_numb) return NO;
  465.     return YES;
  466.     }
  467.  
  468. struct node *select_most_proving_node(struct node *node)
  469.     {
  470.     short i,flag,depth=0;
  471.  
  472.     currsym=rootsym;
  473.  
  474.     while(node->expanded)
  475.         {
  476.         i=0;
  477.         flag=FALSE;
  478.  
  479.         switch(node->type)
  480.             {
  481.             case OR_TYPE:
  482.                 do
  483.                     {
  484.                     if(node->child[nodeseq[i]] &&
  485.                         node->child[nodeseq[i]]->proof==node->proof)
  486.                             flag=TRUE;
  487.                     else i++;
  488.                     } while(i<BOARDX && !flag);
  489.  
  490.                 if(!flag)
  491.                     fatal_error("Could not find a good OR child!");
  492.                 break;
  493.  
  494.             case AND_TYPE:
  495.                 do
  496.                     {
  497.                     if(node->child[nodeseq[i]] &&
  498.                          node->child[nodeseq[i]]->disproof==node->disproof)
  499.                             flag=TRUE;
  500.                     else i++;
  501.                     } while(i<BOARDX && !flag);
  502.  
  503.                 if(!flag)
  504.                     fatal_error("Could not find a good AND child!");
  505.                 break;
  506.  
  507.             default:
  508.                 fatal_error("Unknown node type!");
  509.                 break;
  510.  
  511.             }
  512.         if(flag)
  513.             {
  514.             short jk;
  515.  
  516.             depth++;
  517.             jk=nodeseq[i]+1;
  518.             if(currsym) jk=(8-jk);
  519.             printf("%d",jk);
  520.  
  521.             if(depth==1) best_keep=jk;
  522.  
  523.             if(node->child[nodeseq[i]]->parent[nodeseq[i]]!=node)
  524.                 currsym^=1;
  525.  
  526.             node=node->child[nodeseq[i]];
  527.             }
  528.         else fatal_error("Null node found!");
  529.         }
  530.  
  531.     while(depth++<32)
  532.         printf(" ");
  533.  
  534.     printf("  ");
  535.  
  536.     if(node->type==OR_TYPE) printf("Or : ");
  537.     else if(node->type==AND_TYPE) printf("And: ");
  538.     else fatal_error("Yes, there's a bug...");
  539.  
  540.     return node;
  541.     }
  542.  
  543. void set_pdv_according_to_children(struct node *node)
  544.     {
  545.     short x,children=0;
  546.  
  547.     for(x=0;x<BOARDX;x++)
  548.         if(node->stack[x]<BOARDY) children++;
  549.  
  550.     if(children==0)
  551.         fatal_error("Father without children but of value unknown");
  552.  
  553.     switch(node->type)
  554.         {
  555.         case AND_TYPE:
  556.             node->proof=children;
  557.             node->disproof=1;
  558.             break;
  559.  
  560.         case OR_TYPE:
  561.             node->proof=1;
  562.             node->disproof=children;
  563.             break;
  564.         }
  565.     }
  566.  
  567. void set_proof_and_disproof_numbers(struct node *node)
  568.     {
  569.     short x;
  570.  
  571.     if(!node) fatal_error("Invalid node choosen");
  572.     else if(node->expanded)
  573.         {
  574.         switch(node->type)
  575.             {
  576.             case AND_TYPE:
  577.                 node->proof=0;
  578.                 node->disproof=MAXVALUE;
  579.                 for(x=0;x<BOARDX;x++)
  580.                     if(node->child[x])
  581.                         {
  582.                         node->proof+=node->child[x]->proof;
  583.                         node->disproof=min(node->disproof,node->child[x]->disproof);
  584.                         }
  585.                 if(node->disproof==0)
  586.                     {
  587.                     if(node->direct) nodes_added++;
  588.                     node->direct=NO;
  589.                     node->proof=MAXVALUE;
  590.                     node->value=DISPROVED;
  591.                     }
  592.                 if(node->proof==0)
  593.                     {
  594.                     if(node->direct) nodes_added++;
  595.                     node->direct=NO;
  596.                     node->value=PROVED;
  597.                     }
  598.                 break;
  599.  
  600.             case OR_TYPE:
  601.                 node->proof=MAXVALUE;
  602.                 node->disproof=0;
  603.                 for(x=0;x<BOARDX;x++)
  604.                     if(node->child[x])
  605.                         {
  606.                         node->proof=min(node->proof,node->child[x]->proof);
  607.                         node->disproof+=node->child[x]->disproof;
  608.                         }
  609.                 if(node->proof==0)
  610.                     {
  611.                     if(node->direct) nodes_added++;
  612.                     node->direct=NO;
  613.                     node->disproof=MAXVALUE;
  614.                     node->value=PROVED;
  615.                     }
  616.                 if(node->disproof==0)
  617.                     {
  618.                     if(node->direct) nodes_added++;
  619.                     node->direct=NO;
  620.                     node->value=DISPROVED;
  621.                     }
  622.  
  623.                 break;
  624.  
  625.             default:
  626.                 fatal_error("I don't know what to prove or disprove!");
  627.                 break;
  628.             }
  629.  
  630.         if(node->proof<0 || node->disproof<0)
  631.             fatal_error("Proof and disproof numbers cannot be lower than zero");
  632.  
  633.         }
  634.     else if(node->evaluated)
  635.         {
  636.         switch(node->value)
  637.             {
  638.             case PROVED:
  639.                 node->proof=0;
  640.                 node->disproof=MAXVALUE;
  641.                 break;
  642.  
  643.             case DISPROVED:
  644.                 node->proof=MAXVALUE;
  645.                 node->disproof=0;
  646.                 break;
  647.  
  648.             case UNKNOWN:
  649.                 set_pdv_according_to_children(node);
  650.                 break;
  651.             }
  652.         }
  653.     else fatal_error("Asked to set a node never evaluated!");
  654.     }
  655.  
  656. void develop_node(struct node *node)
  657.     {
  658.     short i;
  659.  
  660.     node->expanded=YES;
  661.  
  662.     generate_all_children(node);
  663.  
  664.     if(!currsym)
  665.         {
  666.         for(i=0;i<BOARDX;i++)
  667.             {
  668.             if(node->child[i])
  669.                 {
  670.                 evaluate(node->child[i]);
  671.                 set_proof_and_disproof_numbers(node->child[i]);
  672.                 }
  673.             }
  674.         }
  675.     else
  676.         {
  677.         for(i=BOARDX-1;i>=0;i--)
  678.             {
  679.             if(node->child[i])
  680.                 {
  681.                 evaluate(node->child[i]);
  682.                 set_proof_and_disproof_numbers(node->child[i]);
  683.                 }
  684.             }
  685.         }
  686.     }
  687.  
  688. void update_ancestors(struct node *node)
  689.     {
  690.     struct node *previous_node;
  691.     short x;
  692.  
  693.     if(node)
  694.         {
  695.         set_proof_and_disproof_numbers(node);
  696.  
  697.         for(x=0;x<BOARDX;x++)
  698.             if(node->parent[x]) update_ancestors(node->parent[x]);
  699.         }
  700.     }
  701.  
  702. /*
  703. struct node *update_ancestors(struct node *node)
  704.     {
  705.     struct node *previous_node;
  706.     short old_proof,old_disproof;
  707.     short changed=YES;
  708.  
  709.     previous_node=NULL;
  710.     while(node && changed)
  711.         {
  712.         old_proof=node->proof;
  713.         old_disproof=node->disproof;
  714.         set_proof_and_disproof_numbers(node);
  715.         changed=((old_proof!=node->proof)||(old_disproof!=node->disproof));
  716.         previous_node=node;
  717.         node=node->parent[0];
  718.         }
  719.  
  720.     return previous_node;
  721.     }
  722. */
  723.  
  724. void pn_search(struct node *root)
  725.     {
  726.     struct node *most_proving_node;
  727.  
  728.     saveflag=NO;
  729.  
  730.     best_keep=0;
  731.     printf("\n");
  732.     printf(" Root evaluation: ");
  733.     evaluate(root);
  734.     set_proof_and_disproof_numbers(root);
  735.     printf("\n");
  736.  
  737.     while(root->proof!=0 && root->disproof!=0 && resources_available())
  738.         {
  739.         saveflag=YES;
  740.         parameters.nodes=node_expanded;
  741.         parameters.end=time(NULL);
  742.         parameters.pr=root->proof;
  743.         parameters.ds=root->disproof;
  744.         parameters.nodes_added=nodes_added;
  745.         show_pinfo();
  746.  
  747.         most_proving_node=select_most_proving_node(root);
  748.         develop_node(most_proving_node);
  749.         update_ancestors(most_proving_node);
  750.         printf("\n");
  751.         }
  752.  
  753.     if(root->proof==0) root->value=PROVED;
  754.     else if (root->disproof==0) root->value=DISPROVED;
  755.     else root->value=UNKNOWN;
  756.  
  757.     dump_pnboard(root);
  758.     }
  759.  
  760. /* ------------------------------------------------------------------- */
  761.  
  762. short start_pn_search(struct board *board)
  763.     {
  764.     char output[200],temps[200];
  765.     short seq[42],seqlen,retval;
  766.     unsigned long tm;
  767.     short hh,mm,ss;
  768.     unsigned char tb[(BOARDX+1)*(BOARDY+2)],ts[BOARDX+1];
  769.     short x,x1,y1,key,cancel_sym;
  770.     FILE *logfile;
  771.  
  772.     for(x=0;x<board->filled;x++)
  773.         seq[x]=board->moves[x]+1;
  774.  
  775.     seqlen=board->filled;
  776.  
  777.     myscreen=(unsigned short *)0xb8000;
  778.     parameters.start=time(NULL);
  779.     timepass=0;
  780.  
  781.     auxboard=board;
  782.     tempboard=(struct board *)malloc(sizeof(struct board));
  783.     if(!tempboard) fatal_error("Cannot store temporary board");
  784.     memcpy(tempboard,board,sizeof(struct board));
  785.  
  786.     clrscr();
  787.  
  788.     max_nodes_numb=MAXNODESNUMB;
  789.  
  790.     printf("\n\nConnect Four Search Engine %s. ",SEARCH_ENGINE_VERSION);
  791.     printf("Last revision %s\n",__DATE__);
  792.     printf("Now building nodes... (each node takes %d bytes of memory)\n",
  793.              sizeof(struct node));
  794.  
  795.     printf("Max nodes numb = %ld  (%ld bytes) ",
  796.               max_nodes_numb,max_nodes_numb*sizeof(struct node));
  797.  
  798.     node_expanded=0L;
  799.     node_not_expanded=0L;
  800.  
  801.     root=(struct node *)malloc(sizeof(struct node));
  802.     if(!root) fatal_error("Not enough memory to begin the search");
  803.  
  804.     for(x=0;x<(BOARDX+1)*(BOARDY+2);x++)
  805.         root->square[x]=(char)(board->square[x]&0xff);
  806.  
  807.     for(x=0;x<BOARDX+1;x++)
  808.         root->stack[x]=(char)(board->stack[x]&0xff);
  809.  
  810.     for(y1=0;y1<BOARDY;y1++)
  811.         {
  812.         tb[ELM(BOARDX,y1)]=root->square[ELM(BOARDX,y1)];
  813.         for(x1=0;x1<BOARDX;x1++)
  814.             tb[ELM(x1,y1)]=root->square[ELM(BOARDX-x1-1,y1)];
  815.         }
  816.  
  817.     ts[BOARDX]=root->stack[BOARDX];
  818.     for(x1=0;x1<BOARDX;x1++)
  819.         ts[x1]=root->stack[BOARDX-x1-1];
  820.  
  821.     cancel_sym=compatible_sym(tb,root->square);
  822.     if(cancel_sym) printf(":-)))\n");
  823.     else printf(":-(((\n");
  824.  
  825.     if(bin_compare(tb,root->square)>0)
  826.         {
  827.         rootsym=YES;
  828.         memcpy(root->square,tb,48);
  829.         memcpy(root->stack,ts,8);
  830.         }
  831.     else rootsym=NO;
  832.  
  833.     root->turn=board->turn;
  834.     root->type=OR_TYPE;
  835.  
  836.     root->evaluated=NO;
  837.     root->expanded=NO;
  838.     root->value=UNKNOWN;
  839.     root->direct=YES;
  840.  
  841.     for(x=0;x<BOARDX;x++)
  842.         root->parent[x]=NULL;
  843.  
  844.     for(x=0;x<BOARDX;x++)
  845.         root->child[x]=NULL;
  846.  
  847.     treeroot=init_bin_tree(root);
  848.     dbroot=init_dbase(root->square,cancel_sym);
  849.  
  850.     nodes_added=0L;
  851.     pn_search(root);
  852.     retval=root->value;
  853.  
  854.     screen_on();
  855.  
  856.     printf("\n\n");
  857.     printf("Search terminated, value found : ");
  858.     sprintf(output,"; vl: ");
  859.  
  860.     switch(root->value)
  861.         {
  862.         case UNKNOWN:
  863.             strcat(output,"unknown; ");
  864.             printf("unknown\n");
  865.  
  866.             sprintf(temps,"BK = %d; ",best_keep);
  867.             strcat(output,temps);
  868.  
  869.             printf("Best Keep = %d\n",best_keep);
  870.             break;
  871.  
  872.         case PROVED:
  873.             strcat(output,"proved; ");
  874.             printf("proved\n");
  875.             break;
  876.  
  877.         case DISPROVED:
  878.             strcat(output,"disproved; ");
  879.             printf("disproved\n");
  880.             break;
  881.         }
  882.  
  883.     if(manual_steer)
  884.         {
  885.         printf("\007\n");
  886.         printf("Do you want to update dbase file ? (Y/N)\n");
  887.         }
  888.  
  889.     parameters.nodes=node_expanded;
  890.     parameters.end=time(NULL);
  891.     parameters.pr=root->proof;
  892.     parameters.ds=root->disproof;
  893.     parameters.nodes_added=nodes_added;
  894.     show_pinfo();
  895.  
  896.     sprintf(temps,"ndu=%ld/%ld; nda=%ld; ",
  897.         node_expanded,max_nodes_numb,nodes_added);
  898.  
  899.     strcat(output,temps);
  900.  
  901.     tm=parameters.end-parameters.start;
  902.  
  903.     hh=(short)(tm/3600);
  904.     mm=(short)((tm/60)%60);
  905.     ss=(short)(tm%60);
  906.  
  907.     sprintf(temps,"time %2d:%02d:%02d\n",hh,mm,ss);
  908.     strcat(output,temps);
  909.  
  910.     if(manual_steer)
  911.         do  {
  912.             key=readkey();
  913.             } while(key!='y' && key!='n');
  914.  
  915.     else
  916.         {
  917.         sleep(2);
  918.         key='n';
  919.         if(root->value==PROVED || root->value==DISPROVED) key='y';
  920.         if(!saveflag) key='n';
  921.         }
  922.  
  923.     if(key=='y')
  924.         {
  925.         if(manual_steer)
  926.             {
  927.             logfile=fopen(DATABASELOGFILE,"a+");
  928.             fprintf(logfile,"Sequence searched : ");
  929.  
  930.             for(x=0;x<seqlen;x++)
  931.                 fprintf(logfile,"%d",seq[x]);
  932.  
  933.             fprintf(logfile,"\n");
  934.             fprintf(logfile,"%s\n",output);
  935.             fclose(logfile);
  936.             }
  937.  
  938.         copy_dbtree();      /* Backup data base file before updating... */
  939.         printf("Updating dbtree\n");
  940.         update_dbtree(treeroot,dbroot,root->turn);
  941.         flush_dbtree(dbroot);
  942.         }
  943.     else printf("Skipping dbtree update...\n\n");
  944.  
  945.     printf("Freeing memory...\n");
  946.     free_dbtree(dbroot);
  947.  
  948.     free_whole_tree(treeroot);
  949.     free_bin_tree(treeroot);
  950.  
  951.     memcpy(board,tempboard,sizeof(struct board));
  952.     free(tempboard);
  953.  
  954.     if(key=='y') shuffle();
  955.  
  956.     erase_temp_file();
  957.  
  958.     printf("Waiting for a key...\n");
  959.     show_pinfo();
  960.  
  961.     if(manual_steer) while(readkey()==0);
  962.     return retval;
  963.     }
  964.  
  965. void output_sequence(FILE *h2,char *seq,short seqlen,short flag)
  966.     {
  967.     char bd[64];
  968.     short stack[7],x,y,z,size=WHITE;
  969.  
  970.     memset(bd,EMPTY,64);
  971.     memset(stack,0,14);
  972.  
  973.     for(z=0;z<seqlen;z++)
  974.         {
  975.         x=seq[z];
  976.         printf("%d",x+1);
  977.  
  978.         if(stack[x]<BOARDY)
  979.             {
  980.             bd[ELM(x,stack[x])]=size;
  981.             stack[x]++;
  982.             size^=SWITCHSIDE;
  983.             }
  984.         else fatal_error("Invalid sequence found");
  985.         }
  986.  
  987.     printf("\n");
  988.  
  989.     bd[63]=(char)flag;
  990.     fwrite(bd,1,64,h2);
  991.     }
  992.  
  993. void build_associated_file()
  994.     {
  995.     FILE *h1,*h2;
  996.     char filein[255],seq[50];
  997.     short seqlen,state=0,byte;
  998.     short seqnumb=1,seqthreshold=0;
  999.     unsigned short key;
  1000.  
  1001.     printf("Input file to parse : ");
  1002.     gets(filein);
  1003.  
  1004.     printf("Start from sequence #1 ? (Y/N)\n");
  1005.     do
  1006.         {
  1007.         key=readkey();
  1008.         if(key=='n' || key=='y') break;
  1009.         } while(1);
  1010.  
  1011.     if(key=='n')
  1012.         {
  1013.         printf("\nEnter sequence number to start from : ");
  1014.         scanf("%d",&seqthreshold);
  1015.         }
  1016.  
  1017.     h1=fopen(filein,"rb");
  1018.     h2=fopen(AUTO_BOOK,"wb");
  1019.  
  1020.     if(!h1 || !h2) fatal_error("File not found");
  1021.  
  1022.     while((byte=getc(h1))!=EOF)
  1023.         {
  1024.         switch(state)
  1025.             {
  1026.             case 0:
  1027.                 if(byte==';') state=1;
  1028.                 else if(byte=='S') state=2;
  1029.                 break;
  1030.  
  1031.             case 1:
  1032.                 if(byte==0x0d) state=0;
  1033.                 break;
  1034.  
  1035.             case 2:
  1036.                 if(byte==0x0d)
  1037.                     {
  1038.                     if(seqlen>0)
  1039.                         output_sequence(h2,seq,seqlen,seqnumb<seqthreshold);
  1040.                     seqlen=0;
  1041.                     state=0;
  1042.                     seqnumb++;
  1043.                     }
  1044.                 else if(byte>='1' && byte<='7' && seqlen<MAXMEN)
  1045.                     seq[seqlen++]=byte-'1';
  1046.  
  1047.                 break;
  1048.             }
  1049.         }
  1050.  
  1051.     fclose(h2);
  1052.     fclose(h1);
  1053.  
  1054.     printf("Work done, press any key!\n");
  1055.     while(readkey()==0);
  1056.     }
  1057.  
  1058. /* ======================================================================= */
  1059.  
  1060. void start_auto_pn_search(struct board *board)
  1061.     {
  1062.     FILE *h1;
  1063.     unsigned char *autobook;
  1064.     long len,size,cnt;
  1065.     short byte,value,x,y,cn,flag=0;
  1066.     struct board *tempboard;
  1067.  
  1068.     clrscr();
  1069.  
  1070.     tempboard=(struct board *)malloc(sizeof(struct board));
  1071.     if(!tempboard) fatal_error("Memory error!");
  1072.  
  1073.     memcpy(tempboard,board,sizeof(struct board));
  1074.  
  1075.     h1=fopen(AUTO_BOOK,"rb");
  1076.     if(!h1) fatal_error("Cannot find autobook");
  1077.  
  1078.     size=fileln(h1);
  1079.     autobook=(unsigned char *)malloc(size);
  1080.     if(!autobook) fatal_error("Memory error");
  1081.  
  1082.     len=0;
  1083.     while((byte=getc(h1))!=EOF)
  1084.         autobook[len++]=byte;
  1085.  
  1086.     fclose(h1);
  1087.  
  1088.     len=0;
  1089.  
  1090.     while(flag==0 && len<size)
  1091.         {
  1092.         printf("Sequence #%ld\n",(len/64)+1);
  1093.  
  1094.         if(autobook[len+63]==1) goto SKIP_ENDING;
  1095.  
  1096.         board->filled=0;
  1097.  
  1098.         for(y=0;y<BOARDY;y++)
  1099.             for(x=0;x<BOARDX;x++)
  1100.                 {
  1101.                 cn=autobook[len+ELM(x,y)];
  1102.                 board->square[ELM(x,y)]=cn;
  1103.                 if(cn!=EMPTY) board->filled++;
  1104.                 }
  1105.  
  1106.         if(board->filled&1) board->turn=BLACK;
  1107.         else                board->turn=WHITE;
  1108.  
  1109.         for(x=0;x<BOARDX;x++)
  1110.             {
  1111.             board->stack[x]=0;
  1112.             while(board->square[ELM(x,board->stack[x])]!=EMPTY &&
  1113.                 board->stack[x]<BOARDY)
  1114.                         board->stack[x]++;
  1115.             }
  1116.  
  1117.         sleep(3);
  1118.         my_t_sequence=(len/64)+1;
  1119.         value=start_pn_search(board);
  1120.         printf("\n\n");
  1121.  
  1122.         if(value==UNKNOWN) flag=1;
  1123.         else if(value==PROVED && board->turn==BLACK) flag=2;
  1124.         else if(value==DISPROVED && board->turn==WHITE) flag=3;
  1125.  
  1126.         if(flag==0)
  1127.             {
  1128.             autobook[len+63]=1;
  1129.             h1=fopen(AUTO_BOOK,"wb");
  1130.             for(cnt=0;cnt<size;cnt++)
  1131.                 putc(autobook[cnt],h1);
  1132.             fclose(h1);
  1133.             }
  1134.  
  1135.         SKIP_ENDING:
  1136.         len+=64;
  1137.         }
  1138.  
  1139.     if(len<size)
  1140.         printf("Work has been either interrupted or computer has found a wrong result\n");
  1141.  
  1142.     else printf("Job has been completed, pal. Hope evrything went well this time!\n");
  1143.  
  1144.     printf("Press RETURN key to continue\n");
  1145.     while(readkey()!=0x0d);
  1146.  
  1147.     free(autobook);
  1148.     memcpy(board,tempboard,sizeof(struct board));
  1149.     free(tempboard);
  1150.     }
  1151.  
  1152.  
  1153.  
  1154.  
  1155.  
  1156.  
  1157.  
  1158.  
  1159.  
  1160.  
  1161.  
  1162.  
  1163.  
  1164.  
  1165.  
  1166.  
  1167.  
  1168.  
  1169.  
  1170.  
  1171.  
  1172.  
  1173.  
  1174.  
  1175.  
  1176.  
  1177.  
  1178.  
  1179.  
  1180.  
  1181.  
  1182.